package com.zhang.study.chapter03;

import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import static com.zhang.util.RandomArrayUtil.generateRandomArray;

/**
 * 使用数组实现队列
 */
public class Code05_ArrayMyQueue {

    /**
     * 使用数组实现队列
     *
     * @param <T>
     */
    public static class ArrayMyQueue<T> {
        public Object[] eleData;
        /**
         * 添加时元素的index
         */
        public int pushIndex;
        /**
         * 弹出元素时的index
         */
        public int popIndex;
        /**
         * 实际大小
         */
        public int fullSize;


        public ArrayMyQueue(int capacity) {
            this.fullSize = 0;
            this.pushIndex = 0;
            this.popIndex = 0;
            this.eleData = new Object[capacity];
        }

        /**
         * 队列尾部添加元素
         *
         * @param ele 添加元素
         */
        public void push(T ele) {
            if (eleData.length == fullSize) {
                throw new RuntimeException("queue is full!");
            }
            fullSize++;
            eleData[pushIndex] = ele;
            pushIndex = nextIndex(pushIndex);
        }

        public T pop() {
            if (fullSize == 0) {
                throw new RuntimeException("queue is empty!");
            }
            fullSize--;
            T ans = (T) (eleData[popIndex]);
            popIndex = nextIndex(popIndex);
            return ans;
        }


        public int nextIndex(int index) {
            // return index == eleData.length - 1 ? 0 : ++index;
            return (index + 1) % eleData.length;
        }

        public static void main(String[] args) {
            int len = 5000;
            int value = 10000;
            int testTime = 10000;

            System.out.println("test begin!");
            for (int i = 0; i < testTime; i++) {
                // 生成链表头结点
                int[] intArr = generateRandomArray(len, value);
                List<Integer> collect = IntStream.of(intArr).boxed().collect(Collectors.toList());
                LinkedList<Integer> linkedList = new LinkedList<>(collect);
                ArrayMyQueue<Integer> myQueue = new ArrayMyQueue<>(intArr.length + 1000);
                for (Integer integer : collect) {
                    myQueue.push(integer);
                }
                if (!testQueue(myQueue, linkedList)) {
                    System.out.println("Oops!");
                }
            }
            System.out.println("test finish!");
        }

        private static boolean testQueue(ArrayMyQueue<Integer> myQueue, LinkedList<Integer> linkedList) {
            int times = linkedList.size() - 1;
            while (times >= 0) {
                double random = Math.random();
                int i = (int) (Math.random() * 100 - Math.random() * 10);
                if (random >= 0.5) {
                    // 从尾部加一个元素
                    myQueue.push(i);
                    linkedList.addLast(i);
                } else {
                    // 从尾部删除一个元素
                    Integer integer = myQueue.pop();
                    Integer integer1 = linkedList.remove();
                    if (!Objects.equals(integer1, integer)) {
                        return false;
                    }
                }
                times--;
            }
            while (!linkedList.isEmpty()) {
                Integer integer = myQueue.pop();
                Integer first = linkedList.removeFirst();
                if (!integer.equals(first)) {
                    return false;
                }
            }
            return true;


        }

    }


}
